778. Swim in Rising Water
Hard

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

  1. 2 <= N <= 50.
  2. grid[i][j] is a permutation of [0, ..., N*N - 1].
Accepted
37,017
Submissions
67,030
Seen this question in a real interview before?
Companies
Show Hint 1
Use either Dijkstra's, or binary search for the best time T for which you can reach the end if you only step on squares at most T.

Average Rating: 4.45 (22 votes)

Premium

Approach #1: Heap [Accepted]

Intuition and Algorithm

Let's keep a priority queue of which square we can walk in next. We always walk in the smallest one that is 4-directionally adjacent to ones we've visited.

When we reach the target, the largest number we've visited so far is the answer.

Complexity Analysis

  • Time Complexity: O(N2logN)O(N^2 \log N). We may expand O(N2)O(N^2) nodes, and each one requires O(logN)O(\log N) time to perform the heap operations.

  • Space Complexity: O(N2)O(N^2), the maximum size of the heap.




Approach #2: Binary Search and DFS [Accepted]

Intuition and Algorithm

Whether the swim is possible is a monotone function with respect to time, so we can binary search this function for the correct time: the smallest T for which the swim is possible.

Say we guess that the correct time is T. To check whether it is possible, we perform a simple depth-first search where we can only walk in squares that are at most T.

Complexity Analysis

  • Time Complexity: O(N2logN)O(N^2 \log N). Our depth-first search during a call to possible is O(N2)O(N^2), and we make up to O(logN)O(\log N) of them.

  • Space Complexity: O(N2)O(N^2), the maximum size of the stack.




Approach #3: Minimal Spanning Tree Algorithm (Union-Find)

Intuition

One can formulate the problem as building a minimum spanning tree, i.e. find minimum edges to connect all nodes in a graph.

In our case, we would like to find the fastest path (i.e. minimal waiting time) to reach from the top-left point to the bottom-right point of the grid.

Rather than finding the spanning tree to connect all cells in the grid, we are only interested to find the spanning that connect our starting and ending points.

One of the well-known algorithms for the minimal spanning tree problem is called Kruskal's algorithm, proposed by Joseph Kruskal in 1956.

So the idea of this solution is to adapt the Kruskal's algorithm to solve our problem here.

Algorithm

The essence of the Kruskal's algorithm relies on the disjoint-set data structure, also known as union-find data structure, which tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

The Kruskal's algorithm starts from a list of sets, where each set contains only a single node, it then greedily merges the sets together until there is only one set left i.e. the minimal spanning tree.

Essentially, the algorithm can be implemented with two major functions: union(a, b) and find(a). With the union(a, b) function, we merge two sets together. And with the find(a) function, we find the representative (also known as parent) of the set.

Here are some overall steps of an adapted Kruskal's algorithm:

  • We consider each cell in the grid as a node in a graph, and the value in the cell represents its weight.

  • We then sort the cells based on their weights, in the ascending order.

  • We then iterate through the sorted cells.

    • At each iteration, we add the neighbor cells around the current cell to the spanning tree.

    • At any moment, if we find that the starting and ending points are connected thanks to the newly added nodes, we exit the loop. And the weight of the current cell would be the minimal waiting time, before we complete the spanning tree.

Here is the solution proposed by leet212. Also, many users have proposed similar ideas and solutions in the discussion forum.

Complexity Analysis

Let NN be the width of the grid (N*N).

  • Time Complexity: O(N2logN2)O(N^2 \log N^2).

    • First of all, we have in total N2N^2 cells in the grid.

    • Since we sort cells based on their weights, it would take O(N2logN2)\mathcal{O}(N^2 \log N^2) time for this sorting operation.

    • We iterate through the cells, i.e. N2N^2 steps. At each step, the union() function requires O(logN2)\mathcal{O}(\log^{*} N^2) complexity, which one can refer to the proof for more details.

    • To sum up, the overall time complexity of the algorithm is O(N2logN2)+O(N2logN2)=O(N2logN2)\mathcal{O}(N^2 \log N^2) + \mathcal{O}(N^2 \log^{*} N^2) = \mathcal{O}(N^2 \log N^2).

  • Space Complexity: O(N2)O(N^2). We use some auxiliary data structures that are proportional to the size of the grid, i.e. N2N^2.



Report Article Issue

Comments: 20
solidhouse4's avatar
Read More

log(N^2) = 2*log(N). ^-^

30
Show 1 reply
Reply
Share
Report
haoyangfan's avatar
Read More

Share my O(n^2) union find solution that only use union find, no heap, dfs, dp or binary search

class Solution {
    
    private static final int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    private int[] parents;
    private int[] ranks;
    
    private void buildUnionFind(int rows, int cols) {
        parents = new int[rows * cols];
        ranks = new int[rows * cols];
        
        for (int i = 0; i < parents.length; ++i) {
            parents[i] = i;
            ranks[i] = 1;
        }
    }
    
    private int find(int id) {
        while (id != parents[id]) {
            parents[id] = parents[parents[id]];
            id = parents[id];
        }
        return id;
    }
    
    private boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    
    private void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        
        if (rootP == rootQ) return;
        
        if (ranks[rootP] <= ranks[rootQ]) {
            parents[rootP] = rootQ;
            ranks[rootQ] += ranks[rootP];
        } else {
            parents[rootQ] = rootP;
            ranks[rootP] += ranks[rootQ];
        }
    }
    
    public int swimInWater(int[][] grid) {
        int N = grid.length;
        buildUnionFind(N, N);
        
        int[] map = new int[N * N];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                map[grid[i][j]] = i * N + j;
            }
        }
        
        for (int time = 0; time < N * N; ++time) {
            int idx = map[time];
            int row = idx / N;
            int col = idx % N;
            
            for (int[] direction : directions) {
                int rr = row + direction[0], cc = col + direction[1];
                if (!isValid(rr, cc, grid, time)) continue;
                union(idx, rr * N + cc);
            }
            
            if (connected(0, N * N - 1)) return time;
        }
        
        return -1;
    }
    
    private boolean isValid(int r, int c, int[][] grid, int time) {
        return r >= 0 && r < grid.length && c >= 0 && c < grid.length && grid[r][c] < time;
    }
}

9
Show 6 replies
Reply
Share
Report
ArizonaTea's avatar
Read More

What does it mean "At time t, the depth of the water everywhere is t"? Everywhere or the cell with lower elevation? It is confusing....

7
Show 1 reply
Reply
Share
Report
anton_smyrnov's avatar
Read More

Another way to solve this problem (more efficiently) is to use Disjoint Set data structure (like in Kruskal's algorithm for finding minimum spanning tree). This way you can reduce time complexity down to O(N^2). We go from 0 to N^2 and choose a Point on the grid with that value. Then we merge it with all its neighbours whose value is less than this Point's value.

7
Show 3 replies
Reply
Share
Report
NotADwarf's avatar
Read More

Is there a proof that the first solution, indeed, finds an optimal solution? It operates in a greedy manner but greedy algos are, in general, not guaranteed to reach the optimal solution.

1
Show 2 replies
Reply
Share
Report
shikhil's avatar
Read More

Can somebody explain the question, i don't get it at all?

1
Reply
Share
Report
zakshevsky's avatar
Read More
1
Reply
Share
Report
NickStartAgain's avatar
Read More

hm.. ok so the binary search solution is based on that we know that lower and upper limit of grid[I][j]. If we don't know && if grid[I][j] is strongly biased, meaning that some 1 s and some 1000000000000 s, binary search probably won't work that well?

0
Show 4 replies
Reply
Share
Report
shushantarora's avatar
Read More

Where is parameter "T" being used in binary search solution in possible function?

Why hi is initialised to N2 isn't it should be max( grid[I][j])

0
Show 1 reply
Reply
Share
Report
anthhht's avatar
Read More

Another solution would be to use Dijstrka. We can use as distance the max. of the current distance and the height of the neighbour. The running time is also O(N^2 log N)

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.